intelligent life Magazine - November/December 2015 | Link
Thinking
Game over -
Computers are not just beating humans; they are solving games entirely. Draughts
has fallen. Tom
Whipple asks if chess will be next
TOM
WHIPPLE | NOVEMBER/DECEMBER 2015
IN THE YEARS following the
publication of J. Sturge’s canonical “Guide to the Game of Draughts” in 1800,
the world of serious players was wracked by argument. Number 105 of Sturge’s
“140 Striking Situations” had asked readers to demonstrate that with the pieces
in a given position white could always win. An expert claimed in a rival
publication that Sturge was wrong: the position was a draw. Another countered
that it was a win for white – but not for the reasons Sturge suggested.
Arguments would continue for the entire reign of Queen Victoria until a
consensus was finally reached: it was a win for white.
This most controversial conundrum in the history of draughts became known as the
Hundred Years Problem. The name was a little premature.
In 1997, a grandmaster showed the Hundred Years Problem to Jonathan Schaeffer,
professor of computer science at the University of Alberta, who is by his own
admission a rather mediocre player. Minutes later, Schaeffer announced that the
result was a draw. This time, there was no controversy, because although
Schaeffer is a mediocre draughts player he is an excellent computer scientist
who had spent the previous decade working on a program, Chinook, designed to
“solve” draughts.
It so happened that in the same year the computer Deep Blue defeated Gary
Kasparov at chess – an event that Newsweek dubbed,
“The Brain’s Last Stand”. In the battle of man versus machine, machine had won a
great victory.
In draughts, though, the brain’s defeat has been much more comprehensive. By
1994 Chinook was already good enough to draw a championship match 6-6 with the
world number one draughts player, Marion Tinsley. Three years later, it
conquered the Hundred Years Problem. Ten years after that, it defeated the game
itself: a paper published in the journal Science showed
that Schaeffer’s program could play a “perfect” game of draughts. Whatever its
opponent did, it would respond with the strongest possible play. While in theory
a better computer program than Deep Blue could come along, the best any future
human or computer could hope to do against Chinook was to draw. The game
contained no further mysteries.
To many players, Chinook’s victory was the game’s loss. Before a game is solved
a skilled player can be considered an artist, driven by inspiration and
creativity as much as by cold logic. Afterwards the player is a fallible human –
imperfectly striving to do what a computer has already done. The success of
Chinook was as if overnight portrait painters had to cope with the invention of
photography, calligraphers with the printing press.
Tinsley was untroubled. He said the program made him feel young again: for
decades he had been unbeatable and at last he had a worthy opponent. But some
draughts players took it badly. “They said I was going to destroy the game, to
ruin it – that no one was going to play,” says Schaeffer. He received hate mail.
Some players argued that the computer’s ability to draw on a database of moves,
rather than computing best play each time, was cheating. Others considered
Schaeffer had besmirched the name of Tinsley, who over a 40-year career lost
fewer than ten games. In particular, they objected to the fact that the program
won against him by default, because he discovered he had terminal cancer halfway
through. “Chinook couldn’t hold a candle to Tinsley,” complained one angry
player in a letter to Schaeffer. Another accused him of “trumpeting an
unjustified victory against a sick old man”, a third of “engaging in
intellectual dishonesty”. A fourth just called him “despicable”.
This upset Schaeffer, who in the course of developing the program had formed a
friendship with Tinsley. “He was as close to perfection as you could imagine a
human being. What some human players were upset about is we now were better than
him.” Schaeffer uses the collective noun a couple of times when referring to him
and Chinook. “He was truly outstanding, but he wasn’t quite perfect. He would
make a mistake. It may have been only once every 10-15 years, but he would make
a mistake.”
Schaeffer is one of a small group around the world trying to solve the world’s
games. Last year, a colleague of his published a paper in which he solved a
simplified version of poker. It ended by quoting Alan Turing: “It would be
disingenuous of us to disguise the fact that the principal motive which prompted
the work was the sheer fun of the thing.”
THERE ARE AROUND 26,830 days
in the average life. If you walked 26,830 miles you would cover the entire
circumference of the equator, and still have enough distance left to go from
Paris to Moscow. There are also 26,830 possible permutations in the first major
game to be solved by a computer. That sounds like a lot, but this is a game so
simple that in America there is a family of animal trainers that raises chickens
to play it against humans as a casino attraction: noughts and crosses.
Most humans have solved noughts and crosses, and the solution is a draw. Writing
a program to play a perfect game of noughts and crosses is now a basic
undergraduate assignment.
A bigger number is 4,531,985,219,092. There have been roughly 4.5 trillion
seconds since humans evolved. When Victor Allis, a computer-science student,
contemplated the number in 1988, he realized it was too big for any computer to
handle. It is, however, the number of possible permutations in Connect 4.
“Computers then were pretty small,” says Allis.
Allis now runs Quintiq, a large Dutch software company. But he still enjoys
talking about Connect 4. Unlike Schaeffer and draughts, he is also rather good
at playing it. When he analyzed why he normally won he realized it was because
of “odd and even threats”: to win you need to have three in a row threatening
completion on an odd row if you are the colour that goes first, and on an even
one if you go second. That knowledge, plus a few other basic strategies and some
clever computing helped him to reduce 4.5 trillion to something more manageable
– and to solve Connect 4.
When it was launched, Connect 4 was marketed as “vertical checkers” – the
American term for draughts. It was a slogan about as sensible as marketing
walking as “horizontal climbing”, for the games are different.
From a computer scientist’s point of view, draughts is 100m times more complex –
with 500 billion billion games. For many people, though, it is more about
emotion. It is like the difference between rounders and baseball, or pool and
snooker. People play Connect 4 for fun; they devote their lives to draughts.
That was why when Allis solved Connect 4 it was an interesting curiosity, but
when Schaeffer solved draughts it was, for some, cataclysmic.
Given how much emotion was generated by the solution of a game that has always
been seen as chess’s less serious cousin, one can only imagine the response when
chess finally falls. Luckily for Schaeffer’s mailbag, he is unlikely to be
around to see that. “We are certainly not going to solve chess in my lifetime,”
he says. “It will need a real change in technology.”
We are used to exponential improvement in computing. After all, in two decades
the hardest game solved by a computer increased in complexity by 100m. So why is
Schaeffer pessimistic about chess?
Five hundred billion billion is big. But the number of atoms in the Earth is
unimaginably big. The number of atoms in the universe is an unimaginably big
number times an unimaginably big number. Chess is so complex that no one is
certain how complex it is – estimates range between these two numbers.
“Very simply expressed, the problem of playing a perfect chess game is that
there are too many possible chess games,” says David Levy, president of the
International Computer Games Association – a body that, despite its title, has
very little to do with Grand Theft Auto – and a lot to do with chess and
draughts. “Remember, the pieces are not all the same. In checkers there are two
pieces – the man and the king. In chess there are six pieces. That is a huge
difference. The game of checkers – I don’t want to use the word ‘simple’ – but
it is simple enough.”
It is hard not to feel there is something marvelous about this. At some point,
more than 1,000 years ago, a game was developed by pre-scientific people – maybe
in China, probably in India – that developed into something confined to a board
eight squares by eight squares, but turned out to be as complicated as the
planet we are on. In the centuries since, almost all other games devised by
humans have been solved by humans – but it has held firm. Levy won’t go so far
as to say it will never be solved. “Never is a very long time,” he says. “Who
knows what might one day be possible? It could be a DNA computer
that will solve it, or an optical computer.” Others have suggested quantum
computers – even more exotic machines that harness the behavior of subatomic
particles. But it is clear that no computer using silicon chips will ever do it.
The question is, if such a computer is devised, and chess at last falls, does
that count as a victory for human ingenuity? Or a defeat? Or maybe, in the end,
like Turing we should just accept it has always been about “the sheer fun of the
thing”.
Tom Whipple is the science editor of the Times
Illustration Brett Ryder
Keywords: GAMES,
COMPUTING